|
The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science. The framework captures problems like factoring, graph isomorphism, and the shortest vector problem. This makes it especially important in the theory of quantum computing because Shor's quantum algorithm for factoring is essentially equivalent to the hidden subgroup problem for finite Abelian groups, while the other problems correspond to finite groups that are not Abelian. ==Problem statement== Given a group ''G'', a subgroup ''H'' ≤ ''G'', and a set ''X'', we say a function ''f'' : ''G'' → ''X'' hides the subgroup ''H'' if for all ''g''1, ''g''2 ∈ ''G'', ''f''(''g''1) = ''f''(''g''2) if and only if ''g''1''H'' = ''g''2''H'' for the cosets of ''H''. Equivalently, the function ''f'' is constant on the cosets of ''H'', while it is different between the different cosets of ''H''. Hidden subgroup problem: Let ''G'' be a group, ''X'' a finite set, and ''f'' : ''G'' → ''X'' a function that hides a subgroup ''H'' ≤ ''G''. The function ''f'' is given via an oracle, which uses ''O''(log |''G''|+log|''X''|) bits. Using information gained from evaluations of ''f'' via its oracle, determine a generating set for ''H''. A special case is when ''X'' is a group and ''f'' is a group homomorphism in which case ''H'' corresponds to the kernel of ''f''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Hidden subgroup problem」の詳細全文を読む スポンサード リンク
|